1. Technical Field
The disclosed embodiments generally relate to the field of image processing.
2. Description of the Related Art
Error diffusion methods, such as the method described in R. W. Floyd & L. Steinberg, “An Adaptive Algorithm for Spatial Grayscale,” in the Proceedings of the Society for Information Display, vol. 17, pp 75-77 (1976) (the “Floyd-Steinberg method”), are often used to convert grayscale images to binary images on a binary output device. Such error diffusion methods typically examine a pixel in an input image, determine whether the intensity for the pixel in the input image exceeds a threshold, and assign either a light or dark binary value to the pixel in an output image based on whether the intensity exceeds the threshold. The difference between the input image pixel intensity and the corresponding pixel intensity in the output image is the error for the pixel. Error diffusion methods assign at least a portion of the error to one or more neighboring pixels that have not been previously assigned a pixel intensity for the output image. In this manner, the total pixel intensity is substantially maintained throughout the output image without a substantial loss of resolution. However, individual pixels might be lighter or darker in the resulting image than in the input image.
For example, FIG. 1A depicts grayscale values for neighboring pixels in an exemplary input image. Each pixel has a grayscale value within a range. In a computer embodiment having 8-bit color, a low value for the range is ‘0,’ and a high value for the range is ‘255.’
FIG. 1B depicts the resulting light/dark values for the four pixels based on a traditional one-dimensional error diffusion method. In FIG. 1B, the threshold for the light/dark determination is the midpoint of the range (i.e., a grayscale value of 127.5). Since the first pixel has a grayscale value greater than the threshold, the pixel is assigned a value of ‘1’ (e.g., “dark” or “black”). The difference between the original grayscale value for the first pixel and the resulting high value is defined to be the error value, E1. In other words, the error is equal to the amount of compensation added to a pixel in order to force it to a ‘0’ or ‘1’ value.
For the second pixel, the error value E1 is subtracted from the original value for the pixel. Since the resulting value is less than the threshold, the second pixel is assigned a value of ‘0’ (e.g., “light” or “white”). The error value, E2, is computed for the second pixel. The process iterates over each subsequent pixel until all pixels are computed. Alternate error diffusion methods might diffuse the calculated error among a plurality of unconverted pixels. For example, a first portion of the error value E1 for the first pixel could be subtracted from the second pixel and a second portion could be subtracted from the third pixel.
Exemplary methods of using error diffusion to generate an output image include the methods described in U.S. Pat. Nos. 5,226,094 and 5,374,997 to Eschbach, the disclosures of which are each incorporated herein by reference in their entireties.
One problem inherent in the Floyd-Steinberg method is that displeasing textures (i.e., worms) are produced in the highlight and shadow regions. An exemplary error diffusion rendered binary output having worm effects is shown in FIG. 2.
Accordingly, modifications to the Floyd-Steinberg method, such as the one described in U.S. Pat. No. 5,353,127 to Shiau et al., which is incorporated herein by reference in its entirety, and shown in FIG. 3, have been developed to reduce this effect. The error diffusion weights (the “Shiau-Fan” or “anti-worm” coefficients) shown in FIG. 3 may be generated using simple bit-shifting techniques. As such, this error diffusion method allows for very fast calculations with limited circuitry.
A third error diffusion method, called “threshold stamping” and described in U.S. Pat. No. 5,535,019 to Eschbach, which is incorporated herein by reference in its entirety, modulates the error diffusion threshold level in order to adjust the dot placement in the extreme highlight and shadow regions. As such, the worm artifact is virtually eliminated. The stamping function uses a line-buffer of memory to store and adjust the slow-scan threshold video that is used to render the downstream pixels via error diffusion processing.
FIG. 4 depicts a block diagram of the main components of a traditional error diffusion color image-processing module with threshold stamping. Each error diffusion block 405a-d performs the threshold stamping and error diffusion algorithms for a particular color, such as cyan, magenta, yellow and black.
The error diffusion blocks 405a-d receive pixel information 410a-d corresponding to the color for each pixel on a scanline. The pixel information 410a-d is within a range, such as from 0 to 255, and represents the intensity of the particular color for the pixel in an input image.
The error diffusion blocks 405a-d also receive error information from the error scanline buffer memory 415a-d corresponding to the same color. Each error value is within a range, such as from −128 to 127, and represents the amount of error passed to the pixel from preceding pixels according to an error diffusion algorithm.
Moreover, the error diffusion blocks 405a-d receive threshold information from the threshold scanline buffer memory 420a-d corresponding to the same color. Each threshold value is within a range, such as from −128 to 127, and represents the change from the base threshold for the particular pixel.
The error diffusion blocks 405a-d determine whether the sum of the pixel value and the error value for a pixel is greater than the sum of the base threshold and the threshold value for the pixel. If the sum of the pixel value and the error value is greater, then the pixel is supplied with the designated color 425a-d. Otherwise, the pixel is not supplied with the designated color.
The error diffusion blocks 405a-d then compute updated error values based on the above comparison for a scanline and store the updated error values in the error scanline buffer memory 415a-d corresponding to the same color. Likewise, the error diffusion blocks 405a-d compute updated threshold values based on the above comparison for a scanline and store the updated threshold values in the error scanline buffer memory 420a-d corresponding to the same color. Accordingly, slow-scan error and threshold information is passed from preceding scanlines to subsequent scanlines using this process.
FIG. 5 depicts a traditional threshold stamping distribution profile that is added to the threshold buffer memory after stamping a “black” (or “dark” pixel) in a light region. The magnitude of the threshold adjustment is typically largest at the central point (TN) of pixel binarization and decays to zero several pixels away (for example, TN+12 and TN−12). As such, this has the desired effect of pushing subsequent printed dot(s) away from a printed dot while still maintaining the overall binary output level. The overall result of this processing shifts the dot placement of surrounding downstream pixels in the opposite direction of the “worm” response. As a result, a visually improved, uniform binary output is delivered. The distribution shown in FIG. 5 represents the effects of one stamped pixel. If multiple pixels are stamped, the threshold scanline buffer memory includes the sum of the threshold adjustments of each stamped pixel.
FIG. 6 depicts an error diffusion threshold delta image. The dark areas correspond to areas in which the threshold delta value is greater than zero for a highlight region. If the location is darker, then the threshold delta value is higher for that location. The slow-scan “decay” of the threshold delta is essential to rendering an adequate binary output dot structure since it is desired that any threshold adjustment only affect the dot-placement of localized “neighboring” pixels while leaving other areas unaffected.
Although threshold stamping improves image quality by improving the location of dots within light regions and holes within dark regions, it is computationally expensive and memory intensive in a number of respects. For example, a damping function is typically used to decay the stamped threshold in the slow path direction. The damping function multiplies the threshold for each bit by a constant. Such multiplication is computationally expensive. The damping function also requires that the threshold values start with a large value to ensure that the stamp effect persists over a sufficient number of lines. In addition, overlapping stamped pixel thresholds are summed, which provides an additional arithmetic operation for each step.
FIG. 7 depicts a block diagram having a reduced threshold scanline buffer memory. As shown in FIG. 7, the threshold stamping function is performed using a register array 705a-y. A majority of the threshold values for a scanline are stored within the threshold scanline buffer memory 720 at any given time. During pixel processing, threshold values are retrieved from the threshold scanline buffer memory 720 and stored within a series of register blocks in the register array 705a-y. 
The register array 705a-y forms a “rolling-buffer” architecture in which information from previous scanlines is retrieved from the error scanline buffer memory 715 and the threshold scanline buffer memory 720, modified by an error diffusion algorithm and a threshold stamping algorithm applied within the register array 705a-y, decayed via the threshold damping circuit 730, and stored within the same memory locations. As such, the threshold and error data are updated for processing by, for example, subsequent scanlines.
The following description pertains to a single instance of an error diffusion algorithm and a threshold stamping algorithm in the register array 705a-y. In operation, FF[+12] 705a receives a pixel intensity value 710, which can be a value within a range from, for example, 0 to 255; an error value from the error scanline buffer memory 715, which can be a value within a range from, for example, −128 to 127; and a threshold value from the threshold scanline buffer memory 720, which can be a value within a range from, for example, −128 to 127. The pixel intensity value 710 represents the pixel intensity of a corresponding pixel in an input image. The error value represents the initial error assigned to the pixel according to an error diffusion algorithm. The threshold value represents a stored threshold value for the pixel based on preceding scanlines. FF[0] (i.e., the error diffusion block) 705m performs error diffusion for a particular pixel.
The size of the threshold scanline buffer memory 720 can be reduced by performing interpolation and extrapolation of the threshold values using threshold upscaling logic 735 and threshold downscaling logic 740. The threshold value may be received from the threshold upscaling logic 735, which may interpolate intermediate threshold values between threshold values stored in the threshold scanline buffer memory 720. Likewise, updated threshold values can be averaged and sampled using threshold downscaling logic 740.
The downscaled threshold value is passed to the threshold damping circuit 730. The threshold damping circuit 730 multiplies the updated threshold value by a value, such as a value between about 0 and about 1. If the resulting value is less than zero, the threshold damping circuit 730 sets the value to 0. The damped threshold value reduces the effect of the threshold delta value on a particular pixel position for each subsequent scanline.
Alternately, the threshold downscaling logic 740 and the threshold damping circuit 730 are combined into one circuit to reduce delay in calculating the damped threshold value.
The damped threshold value and the error value are stored in the same memory location within the threshold scanline buffer memory 720 and the error scanline buffer memory 715, respectively, from which they were originally retrieved. The values are used, for example, in the computation of the threshold and error values for the next scanline.
Because threshold values from overlapping pixel stamps can sum to large values and/or because the threshold values that are stamped typically have large values (such as 8 bits per pixel), the amount of memory required to store the thresholds for an entire scanline is large. As such, the memory required to implement stamping functions can be excessive for particular implementations.
What is needed is an error diffusion method and system that enables high-speed error diffusion while performing stamping.
A need exists for an error diffusion method and system that reduces the worm effects traditionally caused in highlight and shadow regions of an image.
A need exists for a method of reducing the number and/or complexity of computations performed during the stamping portion of an error diffusion process.
A further need exists for a method of reducing the memory size and number of memory accesses for an error diffusion algorithm while substantially maintaining image quality.
The present disclosure is directed to solving one or more of the above-listed problems.